from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


"""
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 
您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/serialize-and-deserialize-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
class Codec:
    def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        """
        if not root: return ""

        left = self.serialize(root.left)
        right = self.serialize(root.right)

        return str(root.val) + ' ' + left + right  # 3_1_2_4_


    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        """
        if not data: return None

        def deserialize_helper(data_list: List[int]) -> TreeNode:
            if len(data_list) == 0: return None

            root_val = data_list[0]
            root = TreeNode(root_val)
            i = 1
            while i<len(data_list) and data_list[i] <= root_val:
                i += 1
            
            root.left = deserialize_helper(data_list[1:i])
            root.right = deserialize_helper(data_list[i:])

            return root
        
        data_list = [int(x) for x in data.split()]  # split() can remove all spaces
        return deserialize_helper(data_list)
